package cn.edu.thu.tsquality.core.algorithm.sequential.dependencies;

import cn.edu.thu.tsquality.core.common.algorithm.IAlgorithm;
import cn.edu.thu.tsquality.core.common.table.Header;
import cn.edu.thu.tsquality.core.common.table.Row;
import cn.edu.thu.tsquality.core.common.table.Table;
import javafx.util.Pair;
import scala.Serializable;

import java.util.*;

/*
顺序依赖检测不精确的数据：
相邻数据之差应满足约束，在[leftBound, rightBound]内
对于一段区间，修改最少的数据点（增大或减小数据），使其满足顺序依赖，那么可以求得这个区间的置信度：
区间置信度为(区间长度-最少需要修改的点的个数)/区间长度


使用动态规划计算最少需要修改的点的个数：
令f(i)表示1-i满足顺序依赖，且不修改第i个数据，最少需要修改的点的个数
更新：f(j)=Min{f(i)+(j-i-1)}，要求i<j 且 y_i + (j-i) * leftBound <= y_j 且 y_i + (j-i) * rightBound >= y_j

使用线段树套平衡树进行优化:
f(j)=Min{f(i)+(j-i-1)}              变成      f(j) - j = Min{f(i) - i} -1
y_i + (j-i) * leftBound <= y_j      变成      y_i - i * leftBound <= y_j - j * leftBound
y_i + (j-i) * rightBound >= y_j     变成      y_i - i * rightBound >= y_j - j * rightBound
变成二维区域求最小值的问题


如果区间满足置信度和支持度，那么记录这个区间内的不精确的点，然后使用其他算法进行修复。

 */
public class SequentialDependencies implements IAlgorithm, Serializable
{
    private String attr;

    // 相邻数据之差在[leftBound, rightBound]内
    private Double leftBound;
    private Double rightBound;

    // 区间需要满足置信度和支持度
    private Double confidenceBound;
    private Integer support;

    // 区间扩大(1+eps)倍
        // 生成区间的长度为：(1+delta)^h 其中 0 < delta <= eps/(2+eps)
    private Double eps;
    private Double delta;

    SequentialDependencies(String attr, Double leftBound, Double rightBound, Double confidenceBound, Integer support, Double eps)
    {
        this.attr = attr;
        this.leftBound = leftBound;
        this.rightBound = rightBound;
        this.confidenceBound = confidenceBound;
        this.support = support;
        this.eps = eps;
        this.delta = eps / (eps+2);
    }

    // 计算区间置信度，为(区间长度-最少需要修改的点的个数)/区间长度
    private double calcConfidence(int left, int right, int editDistance)
    {
        double len = right - left + 1;
        return (len - editDistance) / len;
    }

    private boolean checkConfidence(int left, int right, int editDistance)
    {
        double confidence = calcConfidence(left, right, editDistance);
        return confidence >= confidenceBound;
    }

    private void print(String str)
    {
        System.out.print(str);
    }

    private void println(String str)
    {
        System.out.println(str);
    }

    // [2^k, 2^(k+1)) -> 2^k
    private int pow2IntFloor(Integer num)
    {
        int base = 1;
        while(base*2 <= num)
        {
            base = base * 2;
        }
        return base;
    }

    // 离散化，二分查找下标，用下标变换
    // 因为Double不精确，所以需要使用下标进行map映射
    private int binarySearch(double value, ArrayList<Double> origin, ArrayList<Integer> map)
    {
        int l = 0, r = origin.size() - 1;
        int mid, ans = 0;
        while(l <= r)
        {
            mid = (l + r) / 2;
            if(origin.get(mid) > value)
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
                ans = mid;
            }
        }
        return map.get(ans);
    }

    public Table run(Table table)
    {

        ArrayList<String> tableRows = new ArrayList<>();
        List tableAttrList = Arrays.asList(table.getHeader().toArray());
        if (!tableAttrList.contains(attr))
            throw new IllegalArgumentException("there is no column named " + attr);
        List<Row> rows = table.getRows();
        for (Row row : rows)
            tableRows.add((String) row.get(attr));
        int inputDataSize = tableRows.size();
        Double[] attrData = new Double[inputDataSize];
        for (int i = 0; i < inputDataSize; i++)
            if (tableRows.get(i).equals(""))
                attrData[i] = 0.0;
            else
                attrData[i] = Double.parseDouble(tableRows.get(i));


        //----------------
//        println(attr + " [" + leftBound + "," + rightBound + "]");
//        println(inputDataSize + "");
//        print("Interval = ");
//        for (Double i : attrData)
//            print(i + " ");
//        println("");
        //-----------------


        // 定义返回数据。
        // 返回table为两列，第一列为源数据，第二列为是否需要修复的标记。
        // 返回数据作为修复算法的输入
        String valueAttr = attr;
        String flagAttr = "needRepair_[" + leftBound + "," + rightBound + "]_" + confidenceBound + "_" + eps;
        Header header = new Header(new String[]{valueAttr, flagAttr});
        List<Row> returnRows = new ArrayList<>();


        // 生成区间
        ArrayList<HashSet<Integer>> intervalSets = new ArrayList<>();
        for (int i = 0; i < inputDataSize; i++)
            intervalSets.add(new HashSet<>());


        // 将区间统一左端点
        for (int power = 0; ; power++)
        {
            int intervalLength = ((Double) Math.pow(1 + delta, power)).intValue();
            int approximateIntervalLength = pow2IntFloor(intervalLength);
            //if (intervalLength == 1)
                //continue;

            //-----------------
//            println((1+delta) + "^" + power +"="+intervalLength);
//            println("approximate="+approximateIntervalLength);
            //-----------------

            for (int i = 0; ; i++)
            {
                int start = (int) Math.round(i * delta * approximateIntervalLength);
                if (start >= inputDataSize)
                    break;

                int end = start + intervalLength - 1;

                if (end >= inputDataSize)
                    end = inputDataSize - 1;

                intervalSets.get(start).add(end);
            }

            if (intervalLength >= inputDataSize)
                break;
        }

        //------
//        for(int i = 0; i < inputDataSize; i++)
//        {
//            print("["+i+"]: ");
//            Set set = intervalSets.get(i);
//            ArrayList<Integer> arrayList = new ArrayList(set);
//            Collections.sort(arrayList);
//            for(Integer one:arrayList)
//                print(one+" ");
//            println("");
//        }
        //------


        // 检查区间是否满足confidence和support

        // 左端点为left，记录最长的区间右端点为intervalEndPoint[left]
        int[] intervalRightPoint = new int[inputDataSize];
        // 左端点为left，记录区间[left, intervalRightPoint[left]]中不需要修改的点的下标
        ArrayList<ArrayList<Integer>> keepIndexLists = new ArrayList<>();

        for (int left = 0; left < inputDataSize; left++)
        {
            //--------
//            {
//                println("left: " + left);
//                print("["+left+"]: ");
//                Set set = intervalSets.get(left);
//                ArrayList<Integer> arrayList = new ArrayList(set);
//                Collections.sort(arrayList);
//                for(Integer one:arrayList)
//                    print(one+" ");
//                println("");
//            }
            //--------

            // 记录不修改i时，使1-i满足SD的最少修改个数
            int[] keepTailCostMemory = new int[inputDataSize];
            // 记录由之前哪个j更新这个i
            int[] updateUsedIndex = new int[inputDataSize];

            // 生成的区间的右端点
            ArrayList<Integer> intervalEndPoints = new ArrayList<>(intervalSets.get(left));
            Collections.sort(intervalEndPoints);
            if (intervalEndPoints.size() == 0)
                break;
            // 枚举区间
            int intervalEndPointsIndex = 0;

            // 记录最长可以满足的区间
            int farthestEndPointIndex = -1;
            keepIndexLists.add(new ArrayList<>());

            updateUsedIndex[left] = -1;
            intervalRightPoint[left] = left;

            if (intervalEndPoints.size() == 0)
                continue;

            int maxRight = intervalEndPoints.get(intervalEndPoints.size() - 1);
            int minCost = maxRight - left;
            int minCostUpdateUsedIndex = maxRight;
            int minCostUpdateUsedLatestIndex = -1;


            //二维数据结构，单点修改，区间查询最小值，每次操作时间复杂度logn*logn
            // 预处理：y-kx的离散化
            ArrayList<ArrayList<Double>> yMinusKX = new ArrayList<>();
            ArrayList<ArrayList<Integer>> maps = new ArrayList<>();
            for(int whichOne = 0; whichOne <= 1; whichOne++)
            {
                yMinusKX.add(new ArrayList<>());
                maps.add(new ArrayList<>());
            }

            // 因为g2>=g1，所以y-g2x<=y-g1x，令y-g2x -> 0, y-g1x -> 1
            // leftBound = g1, rightBound = g2
            for(int i = 0; i <= maxRight - left; i++)
            {
                double y = attrData[left + i];
                int x = i;
                yMinusKX.get(0).add(y - rightBound * x);
                yMinusKX.get(1).add(y - leftBound * x);
            }
            Collections.sort(yMinusKX.get(0));
            Collections.sort(yMinusKX.get(1));

            for(int whichOne = 0; whichOne <= 1; whichOne++)
            {
                int double2Int = 0;
                for(int i=0; i < yMinusKX.get(whichOne).size(); i++)
                    if(i == 0 || Math.abs(yMinusKX.get(whichOne).get(i) - yMinusKX.get(whichOne).get(i-1)) > 1e-8)
                        maps.get(whichOne).add(++double2Int);
                    else
                        maps.get(whichOne).add(double2Int);
            }

//            println(yMinusKX.get(0).toString());
//            println(maps.get(0).toString());
//            println(yMinusKX.get(1).toString());
//            println(maps.get(1).toString());

            SegmentTree tree = new SegmentTree(maps.get(0).size());

            for (int right = left; right <= maxRight; right++)
            {
                updateUsedIndex[right] = -1;
                keepTailCostMemory[right] = 0;

                // 用二维数据结构快速查找最小值及其对应的updateIndex
                // 需要找到 outerPosition >= maps[0][y-g2x] InnterPosition <= maps[1][y-g1x]中的最小值
                // 这个值是f(i)-i，由于f(i)-i = Min{f(j)-j} - 1。
                // 0 <= f(i) <= i-1

                double y = attrData[right];
                int x = right - left;
                //int outerL = maps.get(0).get(y - rightBound * x);
                int outerL = binarySearch(y-rightBound*x, yMinusKX.get(0), maps.get(0));
                int outerR = maps.get(0).size();
                int innerL = 1;
                //int innerR = maps.get(1).get(y - leftBound * x);
                int innerR = binarySearch(y-leftBound*x, yMinusKX.get(1), maps.get(1));
                Pair<Integer, Integer> pair = tree.query(outerL, outerR, innerL, innerR);
                int minValue = pair.getKey();
                int updateIndex = pair.getValue();

                if(keepTailCostMemory[right] > minValue - 1)
                {
                    keepTailCostMemory[right] = minValue - 1;
                    updateUsedIndex[right] = updateIndex;
                }

                tree.insert(outerL, innerR, keepTailCostMemory[right], right);

                // 顺便记录最小值的答案，因为minValue = f(i)-i，所以minValue+n = f(i)-i+n 也就是一个ans的值
                // 但是对于不同的区间n值不同，所以我们只记录最小的f(i)-i
                if(keepTailCostMemory[right] < minCost)
                {
                    minCost = keepTailCostMemory[right];
                    minCostUpdateUsedLatestIndex = right;
                }
                //-----
//                println("["+left+","+right+"]");
//                println(" query["+outerL+","+outerR+"] ["+innerL + "," + innerR +"] = (" + minValue + "," + updateIndex+")" );
//                println(" insert["+outerL+","+innerR+"] ("+(keepTailCostMemory[right] - x)+"),"+ right+")");
//                println(" keepTailCost["+right+"]="+(keepTailCostMemory[right] + right - left));
//                println(" minCost="+minCost);
                //-----


                // 如果right==当前生成区间的右端点，那么计算这个区间是否满足，然后计算下一个生成的区间
                if (intervalEndPoints.get(intervalEndPointsIndex) == right)
                {

                    if (checkConfidence(left, right, minCost + right - left))
                    {
                        farthestEndPointIndex = intervalEndPointsIndex;
                        minCostUpdateUsedIndex = minCostUpdateUsedLatestIndex;
                    }
                    //--------
//                    println("intervalEndPoints["+intervalEndPointsIndex+"]="+right);
//                    println("confidence("+left+","+right+","+(minCost+right-left)+")="+checkConfidence(left, right, minCost+right-left));
//                    println("farest end point="+right);
                    //-----


                    // 当前区间计算完成，转到下一个区间
                    intervalEndPointsIndex++;

                    // 左端点为left的所有区间都计算完成？
                    if (intervalEndPointsIndex == intervalEndPoints.size())
                    {

                        if (farthestEndPointIndex != -1)
                        {
                            // 记录可以满足SD的最远右端点
                            intervalRightPoint[left] = intervalEndPoints.get(farthestEndPointIndex);

                            //--------------------------
//                            for(int i = left; i <= intervalRightPoint[left]; i++)
//                                println("lastUpdate["+i+"]="+updateUsedIndex[i] );
//
//                            int temp = intervalRightPoint[left] - left;
//                            for (int i = left; i <= intervalRightPoint[left]; i++)
//                                if (temp > intervalRightPoint[left] -left + keepTailCostMemory[i])
//                                    temp = intervalRightPoint[left] -left + keepTailCostMemory[i];
//
//                            println("[" + left + "," + intervalRightPoint[left] + "]="
//                                    + calcConfidence(left, intervalRightPoint[left], temp));
//                            for (int i : keepIndexLists.get(left))
//                                print(" " + i);
//                            println("");
                            //--------------------------

                            // 记录这个区间内不用修改的点的个数

                            for (int i = minCostUpdateUsedIndex; i != -1; i = updateUsedIndex[i])
                                keepIndexLists.get(left).add(i);
                            Collections.sort(keepIndexLists.get(left));
                            //-----------------------------
//                            print(" "+keepIndexLists.get(left).size()+" [");
//                            for(int i : keepIndexLists.get(left))
//                                print(i+" ");
//                            println("]");
                            //-----------------------------
                        }

                        break;
                    }

                }
            }



/*

            // 枚举 n^2
            for (int right = left; right <= maxRight; right++)
            {
                updateUsedIndex[right] = -1;
                keepTailCostMemory[right] = right - left;

                // 暴力枚举满足条件的点
                // 对于长度为n的序列，时间复杂度n*n
                for (int updateIndex = left; updateIndex < right; updateIndex++)
                {
                    // 可以由attrData[update]经过(right-updateIndex)步的变化，变成attrData[right]
                    if (attrData[updateIndex] + (right - updateIndex) * leftBound <= attrData[right]
                            && attrData[updateIndex] + (right - updateIndex) * rightBound >= attrData[right])
                    {
                        // 是否有修改个数更少的方案？
                        if (keepTailCostMemory[right] > keepTailCostMemory[updateIndex] + right - updateIndex - 1)
                        {
                            keepTailCostMemory[right] = keepTailCostMemory[updateIndex] + right - updateIndex - 1;
                            updateUsedIndex[right] = updateIndex;
                        }
                    }
                }

                // 如果right==当前生成区间的右端点，那么计算这个区间是否满足，然后计算下一个生成的区间
                if (intervalEndPoints.get(intervalEndPointsIndex) == right)
                {

                    int ans = inputDataSize;

                    for (int i = left; i <= right; i++)
                        if (ans > right - i + keepTailCostMemory[i])
                        {
                            ans = right - i + keepTailCostMemory[i];
                            if (checkConfidence(left, right, ans))
                            {
                                farthestEndPointIndex = intervalEndPointsIndex;
                                minCost = ans;
                                minCostUpdateUsedIndex=i;
                            }
                        }


                    // 当前区间计算完成，转到下一个区间
                    intervalEndPointsIndex++;

                    // 左端点为left的所有区间都计算完成？
                    if (intervalEndPointsIndex == intervalEndPoints.size())
                    {
                        if (farthestEndPointIndex != -1)
                        {
                            // 记录可以满足SD的最远右端点
                            intervalRightPoint[left] = intervalEndPoints.get(farthestEndPointIndex);

                            //--------------------------
//                            for(int i = left; i <= intervalRightPoint[left]; i++)
//                                println("lastUpdate["+i+"]="+updateUsedIndex[i] );
//
//                            int temp = intervalRightPoint[left] - left;
//                            for (int i = left; i <= intervalRightPoint[left]; i++)
//                                if (temp > intervalRightPoint[left] - i + keepTailCostMemory[i])
//                                    temp = intervalRightPoint[left] - i + keepTailCostMemory[i];
//
//                            println("[" + left + "," + intervalEndPoints.get(farthestEndPointIndex) + "]="
//                                    + calcConfidence(left, intervalRightPoint[left], temp));
//                            for (int i : keepIndexLists.get(left))
//                                print(" " + i);
//                            println("");
                            //--------------------------

                            // 记录这个区间内不用修改的点的个数
                            for (int i = minCostUpdateUsedIndex; i != -1; i = updateUsedIndex[i])
                                keepIndexLists.get(left).add(i);
                            Collections.sort(keepIndexLists.get(left));

                            //-----------------------------
//                            print(" "+keepIndexLists.get(left).size()+" [");
//                            for(int i : keepIndexLists.get(left))
//                                print(i+" ");
//                            println("]");
                            //-----------------------------
                        }

                        break;
                    }

                }
            }

*/


        }

        // 区间合并
        ArrayList<Pair<Integer, Integer>> intervals = new ArrayList<>();
        int intervalLeft = -1;
        int intervalRight = -1;
        for(int i = 0; i < inputDataSize; i++)
        {
            // has an interval
            if(intervalRightPoint[i] != -1)
            {
                if(intervalLeft == -1)
                {
                    intervalLeft = i;
                    intervalRight = intervalRightPoint[i];
                }
                else if(intervalRight < intervalRightPoint[i])
                {
                    if(intervalRight - intervalLeft + 1 >= support)
                        intervals.add(new Pair<>(intervalLeft, intervalRight));
                    intervalLeft = i;
                    intervalRight = intervalRightPoint[i];
                }
            }
        }
        if(intervalLeft != -1 && intervalRight - intervalLeft + 1 >= support)
            intervals.add(new Pair<>(intervalLeft, intervalRight));

        //----------
//        for(Pair<Integer, Integer> pair : intervals)
//            println("["+pair.getKey()+","+pair.getValue()+"]");
        //----------

        // 合并后区间内需要修复的点进行标记
        boolean[] needRepair = new boolean[inputDataSize];
        for(int i = 0; i < inputDataSize; i++)
            needRepair[i] = false;
        for(Pair<Integer, Integer> pair : intervals)
        {
            int left = pair.getKey();
            int right = pair.getValue();
            for(int i = left; i <= right; i++)
                if (!keepIndexLists.get(left).contains(i))
                    needRepair[i] = true;
        }

        for(int i = 0; i <inputDataSize; i++)
            returnRows.add(new Row(header,
                    new String[]{
                            tableRows.get(i),
                            String.format("%d", needRepair[i]?1:0)
                    }, i));
        return new Table(header, returnRows);
    }
}